// 创建HashTable构造函数
function HashTable() {

    // 定义属性
    this.storage = [];
    // 哈希表已有的元素数量
    this.count = 0;
    // 哈希表的空间
    this.limit = 7;

    // 设计哈希函数
    // 将字符串转成比较大的数字 hashCode
    // 将大的数字hashCode压缩到数组范围内
    HashTable.prototype.hashFunc = function (str, size) {
        // 定义hashCode变量
        var hashCode = 0;

        // 霍纳法则，用来计算hashCode值
        // charCodeAt获取的是unicode编码的值
        for (var i = 0; i < str.length; i++) {
            hashCode = hashCode * 37 + str.charCodeAt(i);
        }

        // 取余操作
        var index = hashCode % size;

        return index;
    }

    // 添加修改操作
    HashTable.prototype.put = function (key, value) {

        // 先将key转成index
        var index = this.hashFunc(key, this.limit);

        // 根据index取出对应的bucket
        var bucket = this.storage[index]

        // 判断bucket是否存在
        if (bucket === undefined) { // 不存在
            // 直接新创一个bucket
            bucket = [];
            this.storage[index] = bucket;
        }

        // 判断是否是修改数据
        for (var i = 0; i < bucket.length; i++) {
            var tuple = bucket[i];
            if (key == tuple[0]) { // 是修改
                tuple[1] = value;
                return 
            }
        }

        // 是添加
        bucket.push([key, value]);
        this.count += 1;

        // 判断是否需要扩容
        if (this.count > this.limit * 0.75) {
            var newSize = this.limit * 2;
            var newPrime = this.getPrime(newSize);
            this.resize(newPrime)
        }
    }

    // 哈希表的获取方法
    HashTable.prototype.get = function (key) {
        
        // 先将key转化为index
        var index = this.hashFunc(key, this.limit);

        // 根据key取bucket
        var bucket = this.storage[index];

        // 判断bucket是否为空
        if (bucket == null) {
            return null;
        }

        // 在bucket中进行查找
        for (var i = 0; i < bucket.length; i++) {
            var tuple = bucket[i];
            if (key = tuple[0]) {
                return tuple[1];
            }
        }

        // 没找到返回null
        return null;
    }

    // 哈希表的删除方法
    HashTable.prototype.remove = function (key) {
        var index = this.hashFunc(key, this.limit);

        var bucket = this.storage[index];
        if (bucket == null) return null;

        for (var i = 0; i < bucket.length; i++) {
            var tuple = bucket[i];
            if (key == tuple[0]) {
                bucket.splice(i, 1);
                this.count -= 1;
                // 判断是否要缩容
                if (this.limit > 7 && this.count < this.limit * 0.25) {
                    var newSize = Math.floor(this.limit / 2);
                    var newPrime = this.getPrime(newSize);
                    this.resize(newPrime);
                }
                return tuple[1];
            }
        }

        return null;
    }

    // isEmpty方法
    HashTable.prototype.isEmpty = function () {
        return this.count == 0
    }

    // size方法
    HashTable.prototype.size = function () {
        return this.count
    }

    // 扩容方法
    HashTable.prototype.resize = function (newLimit) {

        var oldStorage = this.storage;
        this.storage = [];
        this.count = 0;
        this.limit = newLimit;

        // 开始将oldStorage里的值重新赋给storage
        // 先取桶
        for (var i = 0; i < oldStorage.length; i++) {
            var bucket = oldStorage[i];

            if (bucket == null) {
                continue;
            }
            // 从桶里取值
            for (var j = 0; j < bucket.length; j++) {
                var tuple = bucket[j];
                this.put(tuple[0], tuple[1]);
            }
        }
    }

    // 判断是否是质数
    HashTable.prototype.isPrime = function (num) {
        var temp = parseInt(Math.sqrt(num));
        // 循环判断
        for (var i = 2; i <= temp; i++) {
            if (num % i == 0) {
                return false;
            }
        }

        return true;
    }

    // 获取质数
    HashTable.prototype.getPrime = function (num) {

        while(!this.isPrime(num)) {
            num++;
        }

        return num;
    }

}

